// 定义二叉树节点类
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    TreeNode answer;
    boolean find;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        find = false;
        toFind(root, p, q);
        return answer;
    }

    // 两种可能：
    // 1.均在左右子树
    // 2.有一个就是此节点
    public boolean toFind(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return false;
        }

        boolean left = toFind(root.left, p, q);
        boolean right = toFind(root.right, p, q);

        if (find) {
            return true;
        }

        // 两数均找到
        if (((root.val == p.val || root.val == q.val)
                && (left || right))
                || (left && right)) {

            answer = root;
            find = true;
            return true;
        }

        // 仅找到一个
        return root.val == p.val || root.val == q.val || left || right;
    }

    // 主方法，用于测试
    public static void main(String[] args) {
        // 构建测试用的二叉树
        //       3
        //      / \
        //     5   1
        //    /|   |\
        //   6 2   0 8
        //     |\
        //     7 4
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(5);
        root.right = new TreeNode(1);
        root.left.left = new TreeNode(6);
        root.left.right = new TreeNode(2);
        root.right.left = new TreeNode(0);
        root.right.right = new TreeNode(8);
        root.left.right.left = new TreeNode(7);
        root.left.right.right = new TreeNode(4);

        Solution solution = new Solution();

        // 测试用例1: 节点5和节点1的最近公共祖先是3
        TreeNode p = root.left;   // 节点5
        TreeNode q = root.right;  // 节点1
        TreeNode lca = solution.lowestCommonAncestor(root, p, q);
        System.out.println("节点 " + p.val + " 和节点 " + q.val + " 的最近公共祖先是: " + lca.val);

        // 测试用例2: 节点5和节点4的最近公共祖先是5
        p = root.left;             // 节点5
        q = root.left.right.right; // 节点4
        solution.find = false;     // 重置查找状态
        lca = solution.lowestCommonAncestor(root, p, q);
        System.out.println("节点 " + p.val + " 和节点 " + q.val + " 的最近公共祖先是: " + lca.val);
    }
}    